C#和.Net框架

题目

题解

• 注意点
  • 数组无序
  • 返回下标

暴力

• 二重循环

  class Solution {
  public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> v;
        for(int i = 0; i < nums.size();++i)
            for(int j = i+1; j < nums.size();++j)
                if(nums[i] + nums[j] == target)
                {
                    v.push_back(i);
                    v.push_back(j);
                }
        return v;
  
    }
  };
  

• 时间复杂度:O($n^{2}$)

• 空间复杂度 O(1)

双指针

• 排序($nlog(n)$)之后使用双指针($O(n)$)找出所求的值
• 所求的是原数组中的下标，所以排序前复制一份。之后利用找到的值来找到下标

• 需要注意从原数组找下标时，下标大小和数值重复的问题。

  class Solution {
  public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> tmp = nums;
        sort(tmp.begin(),tmp.end());
  
        int i = 0;
        int j = tmp.size()-1;
  
        while(i < j)
        {
            if(tmp[i] + tmp[j] > target) --j;
            else if(tmp[i] + tmp[j] < target) ++i;
            else break;
        }
  
        bool bi = false;
        bool bj = false;
        for(int k = 0; k < nums.size();++k)
        {
            if(!bi && nums[k] == tmp[i] )
            {
                i=k;
                bi = true;
                continue;
            }
  
            if(!bj && nums[k] == tmp[j])
            {
                j = k;
                bj = true;
                continue;
            }
        }
  
        if(i > j)
            swap(i,j);
  
        return {i,j};
    }
  };
  

• 时间复杂度: $O(nlog(n) + n + n) = O(nlog(n))$

• 空间复杂度: $O(n)$

两遍哈希

• 利用map或unordered_map将数组中的值和下标关联在一起。
  • 这里会注意到一点，可能数组中的值会重复，导致一个值关联多个下标，而实际代码中的结果会使得最后一个重复值关联相应下标。
  • 但是这并不会影响结果。如此考虑，因为结果唯一，所以结果要取重复值，则数组中该结果对应的重复值有且仅有2个，不然不满足结果唯一。
  • 所以在查找的时候，用的是原数组进行迭代，所以重复的第一个值要找的就是重复的后一个值，所以上述正好满足我们的要求

• 利用原数组进行查找 target - nums[i] 是否在map中,map::find为O(log(n))，其基于红黑树。unordered_map::find()为O(1),其基于哈希表

  class Solution {
  public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> m;
        for(int i =0; i < nums.size();++i)
            m[nums[i]] = i;
  
        for(int i =0; i < nums.size();++i)
        {
            if(m.find(target-nums[i]) != m.end() && m[target-nums[i]] != i)
                return {i,m[target-nums[i]]};
        }
        return {};
    }
  };
  

• 时间复杂度:map:$O(nlog(n))$、unordered_map:$O(n)$
• 空间复杂度:o(n)

一遍哈希

• 利用map或unordered_map将数组中的值和下标关联在一起。

• 在这里直接循环原数组，查找map中否有target - nums[i]。没有的话加入map中。

  class Solution {
  public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> m;
  
        for(int i =0; i < nums.size();++i)
        {
            if(m.find(target-nums[i]) != m.end())
            {
                return {m[target-nums[i]],i};
            }
            else
            {
                m[nums[i]] = i;
            }
        }
  
        return {};
    }
  };
  

• 时间复杂度:map:$O(nlog(n))$、unordered_map:$O(n)$
• 空间复杂度:o(1)